﻿public class Solution39_2
{
    IList<IList<int>> res = new List<IList<int>>();
    public IList<IList<int>> CombinationSum(int[] candidates, int target)
    {

        IList<int> path = new List<int>();
        DFS(candidates, target, 0, path);
        return res;
    }
    void DFS2(int[] candidates, int target, int start, IList<int> path)
    {

        if(start >= candidates.Length)
        {
            return;
        }
       

        if (target < 0)
        {
            return;
        }
        if (target == 0)
        {


            res.Add(new List<int>(path));
            return;
        }
        path.Add(candidates[start]);

        DFS(candidates, target - candidates[start], start, path);//选择
        path.RemoveAt(path.Count - 1);

        DFS(candidates, target, start + 1, path);//选下一个
    }

    void DFS(int[] candidates, int target, int start, IList<int> path)
    {

        if (start >= candidates.Length)
        {
            return;
        }


        if (target < 0)
        {
            return;
        }
        if (target == 0)
        {


            res.Add(new List<int>(path));
            return;
        }

        for(int i = start; i < candidates.Length; i++)
        {

            path.Add(candidates[i]);

            DFS(candidates, target - candidates[i], i, path);//选择
            path.RemoveAt(path.Count - 1);

           

        }
      
    }

}
class Program39_2
{






    static void Main39_2(string[] args)
    {



        int[] nums = [2, 3, 6, 7];
        Solution39_2 solution = new ();
        IList<IList<int>> res = solution.CombinationSum(nums, 7);
      
    }
}